package leetcode_400;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;

/**
 *@author 周杨
 *InsertDeleteGetRandomO1_DuplicatesAllowed_381  跟上题一样 可以添加重复元素
 *describe:用List和Map完成  AC 98%
 *2018年7月11日 上午11:15:06
 */
public class InsertDeleteGetRandomO1_DuplicatesAllowed_381 {
	private Map<Integer, Set<Integer>> map ;
	private List<Integer> list ;
    private Random rand = new Random();

    /** Initialize your data structure here. */
    public InsertDeleteGetRandomO1_DuplicatesAllowed_381() {
    	this.map= new HashMap<>();
    	this.list= new ArrayList<>();
    }
    
    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        if (!map.containsKey(val)) {
            map.put(val, new HashSet<>());
        }
        map.get(val).add(list.size());
        list.add(val);
        return map.get(val).size() == 1;
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        if (!map.containsKey(val) || map.get(val).isEmpty()) return false;
        int i = map.get(val).iterator().next();
        map.get(val).remove(i);//删除第一个元素
        if (i < list.size() - 1) {
            int last = list.get(list.size() - 1);
            list.set(i, last);//将list与其相同的后一个元素放在这里
            map.get(last).remove(list.size() - 1);
            map.get(last).add(i);
        }
        list.remove(list.size() - 1);
        return true;
    }
    
    /** Get a random element from the collection. */
    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }

}
